	/*
	*
	*	The Gimme ECMAScript Library by Stephen Stchur
	*	"Taking the pain out of Javascript!"
	*
	*	Copyright (c) Microsoft Corporation.  All rights reserved.
	*
	*	Description:
	*	Fetch: the CSS Querying Engine used in the Gimme Javascript Library
	*
	*	Requires:
	*	Nothing
	*
	*	Coding Conventions:
	*	1. Private member variables are prefixed with an underscore
	*	2. Private methods/functions are camelCase
	*	3. Publicly exposed methods/function are camelCase, and getters/setters are prefixed with get_ and set_
	*	4. Properties acting as "namespaces" for other properties and functions are TitleCase
	*
	*/

	var fetch = function()
	{
		// private members
		var _uniqueBit;
		var _genSibBit;
		var _nthBit;
		var _fetchRules;
		var _parseRules;
		var _parser;
		////
		
		
		// private methods
		function search(collection, relationship, ss)
		{
			return _fetchRules[relationship](collection, ss);			
		}
		
		function getDescendants(root, elems)
		{
			var matched = [];
			var len = elems.length;
			do
			{
				var elem = getDescendant(root, elems[--len] || elems);
				elem && matched.push(elem);
			}
			while (len)
			return matched;
		}
		
		function getDescendant(root, elem)
		{
			if (root === document || !elem) return elem;
			var desc = elem;
			while ((desc = desc.parentNode) && desc !== root);
			return desc === root && elem || null;		
		}
		
		function getDescendantById(root, id)
		{
			return getDescendant(root, document.getElementById(id));
		}
		
		function simpleFetch(ss, root)
		{
			root = root || document;
			
			if (ss.id)
			{
				return filter([ getDescendantById(root, ss.id) ], ss);
			}
			
			delete ss.id;
			var elems = root.getElementsByTagName(ss.tag || '*');
			
			// optimization technique, TODO: make this generic
			if ((!ss.classes || ss.classes.length < 1)
				&& (!ss.attributes || ss.attributes.length < 1)
				&& (!ss.pseudos || ss.pseudos.length < 1))
				//&& (!rules.customExists))
			{
				return makeArray(elems);
			}
			
			var matched = [];
			var i, len = elems.length;
			for (i = 0; i < len; i++)
			{
				processSelector(ss, elems[i]) && matched.push(elems[i]);
			}

			return matched;			
		}
		
		function processSelector(ss, elem)
		{
			if (!elem) return false;
			
			var props = ss.propNames
			var i, len = props.length;
			for (i = 0; i < len; i++)
			{
				if (!_fetchRules[props[i]](elem, ss[props[i]])) return false;
			}
			return true;
			
			/*
			var rule;
			for (rule in ss)
			{
				if (ss.hasOwnProperty(rule) && !rules[rule](elem, ss[rule])) return false;
			}
			return true;
			*/
			
			/*
			return elem
				&& (!ss.id || rules['id'](elem, ss.id))
				&& (!ss.tag || rules['tag'](elem, ss.tag))
				&& (!ss.classes || ss.classes.length === 0 || rules['classes'](elem, ss.classes))
				&& (!ss.attributes || ss.attributes.length === 0 || rules['attributes'](elem, ss.attributes))
				&& (!ss.pseudos || ss.pseudos.length === 0 || rules['pseudos'](elem, ss.pseudos));
			*/		
		}
		
		function makeArray(collection)
		{
			var arr = [];
			var i, len = collection.length;
			for (i = 0; i < len; i++)
			{
				arr[i] = collection[i];				
			}
			return arr;		
		}
		
		function filter(collection, ss)
		{
			var matched = [];
			var i, len = collection.length;
			for (i = 0; i < len; i++)
			{
				collection[i] && collection[i].nodeType === 1 && processSelector(ss, collection[i]) && matched.push(collection[i]);
			}
			return matched;		
		}
		
		var indexOf = function()
		{
			return typeof Array.prototype.indexOf !== 'undefined' ? native_indexOf : custom_indexOf;

			function native_indexOf(collection, item)
			{
				return collection.indexOf(item);
			}

			function custom_indexOf(collection, item)
			{
				var i, len = collection.length;
				for (i = 0; i < len; i++)
				{
					if (collection[i] === item)
					{
						return i;
					}
				}
				return -1;
			}
		}();

		function contains(collection, item)
		{
			return indexOf(collection, item) !== -1;
		}

		function unique(collection)
		{
			_uniqueBit.inc();
			var name = _uniqueBit.name;
			
			var uniqueCollection = [];
			var i, len = collection.length;
			for (i = 0; i < len; i++)
			{
				var elem = collection[i];
				if (elem[name] !== _uniqueBit.t)
				{
					elem[name] = _uniqueBit.t;
					uniqueCollection.push(elem);
				}
			}

			return uniqueCollection;
		}
		
		var getAttr = function()
		{
			return function()
			{
				// In most w3c browser (FF, Chrome, Safari, Opera, IE9),
				// retrieving attribute values behaves in a predictable way.
				// That is, "what you set is what you get."  If the your HTML
				// set href = "#test", you get back "#test"
				// If IE < 9, this isn't so.  Older version of IE like to
				// "fix" your attribute values for you (in most cases, it seems
				// the browser is trying to normalize them).  In the same example
				// in IE < 9, you'd get back "http://the.full.domain/page.ext#test"
				// which is pretty obviously wrong.
				//
				// The ie function below attempts several work-arounds to combat
				// this problem, but IE9+ doesn't need any of them.  It can be
				// routed through to the standards-compliant function just like
				// every other modern, well-behaved browser.
				//
				// The check below is an attempt to check the browser's behavior
				// around the native .getAttribute function and route appropriately.
				
				var tmp = document.createElement('div');
				tmp.innerHTML = '<a href="#test">test</a>';
				var a = tmp.firstChild;
				return a.getAttribute('href') === '#test' ? w3c : ie;
			}();

			function w3c(_elem, _attr)
			{
				return _elem.getAttribute(_attr);
			}

			function ie(_elem, _attr)
			{
				switch (_attr.toLowerCase())
				{
					case 'class':
						return _elem.className || null;

					case 'id':
						return _elem.id || null;

					case 'href':
					case 'src':
						// IE Bug: when a '#default#userData' behavior is bound to an element, getAttribute fails to return anything useful.
						// Worse, it throws a run-time error if you try to invoke it with an iFlag parameter, as in: .getAttribute('href', 2);
						// Even more odd, typeof .getAttribute in this case returns "unknown" ( ?? what the heck! )
						// We can leverage this oddity, to avoid invoking .getAttribute(..) with an iFlag parameter.  In that case, we fall back
						// to trying to retrieve the attribute value through the element's .attributes collection.
						if (typeof _elem.getAttribute !== 'undefined')
						{
							// If typeof .getAttribute is not "unknown" we can safely use iFlag parameters when invoking .getAttribute(..).
							// It still might return null though, (in IE) so a series of logical ORs will help increase our chances of
							// retrieving the desired attribute value.
							return _elem.getAttribute(_attr, 2);
						}
						break;

					default:
						break;
				}

				return _elem.attributes && _elem.attributes[_attr] && _elem.attributes[_attr].nodeValue || _elem.getAttribute(_attr);
			}
		}();
	
		////
		
		
		// private "classes"
		function CacheBit(name)
		{
			this.name = name;
			this.f = 0;
			this.t = 1;
			this.inc = function()
			{
				this.f = (this.t += 2) - 1;
			}		
		}
		
		// CSS Parser
		function CSSParser(rules)
		{
			this.parse = function(input)
			{
				var c, rule, advance;
				var ppi = rules['preprocessInput'];
				input = ppi && ppi(input) || input;
				
				rules['reset']();
				
				var i = 0, len = input.length;
				while (i < len)
				{
					c = input.charAt(i);
					rule = rule || rules[c] || rules['default'];
					if (rule)
					{
						advance = rule(input.substring(i, len));
						if (!advance)
						{
							throw 'No valid match found for "' + rule.name + '" rule';
						}
						i += advance;
					}
					else
					{
						throw 'No suitable rule found to handle character "' + c + '"';
					}
					
					rule = null;				
				}
				
				return rules['finish']();
			}
		}
		////
		
		// the actual fetch function
		function fetch(selector, root)
		{
			var originalRoot = root;
			root = root || document;
		
			_nthBit.inc();
			
			if (typeof selector !== 'string')
			{
				return getDescendants(root || document, selector);
			}
			
			var elems, union = [];			
			try
			{
				union = makeArray(root.querySelectorAll(selector));
			}
			catch (everything)
			{
				var selectors = _parser.parse(selector);
				var i, selectorCount = selectors.length;
				for (i = 0; i < selectorCount; i++)
				{
					var args = selectors[i];
					var len = args.length;
					var j = (len % 2) - 1;
					elems = j === 0 ? simpleFetch(args[j], root) : [ root || document ];
					while (args[++j])
					{
						var combinator = args[j++];
						var rhss = args[j];
					
						// Bit of a hack, but the root needs to be stuffed into the simple selector so that,
						// if a root is specified, it can be accounted for in throughout the entire fetching process
						rhss.root = root;
					
						elems = search(elems, combinator, rhss);
					}
					
					// don't bother with .concat if there is only one selector in the selectors array
					union = selectorCount > 1 ? union.concat(elems) : elems;
				}
			}
			
			return union;
		}		
		////
		
		
		// "constructor"
		_uniqueBit = new CacheBit('__$gimme$_unique__');
		_genSibBit = new CacheBit('__$gimme$_genSib__');
		_nthBit = new CacheBit('__$gimme$_nth__');
		
		_fetchRules =
		{
			'id': function(elem, id)
			{
				return elem.id === id;
			},
			
			'tag': function(elem, tag)
			{
				return elem.tagName === tag || tag === '*';
			},
			
			'classes': function(elem, classes)
			{
				var className = elem.className;
				if (typeof className !== 'string')
				{
					className = getAttr(elem, 'class');
				}
				
				if (!className)
				{
					return false;
				}

				var elemClass = ' ' + className + ' ';
				var i = classes.length;
				while (i--)
				{
					if (elemClass.indexOf(' ' + classes[i] + ' ') === -1)
					{
						return false;
					}
				}
				return true;
			},
					
			'attributes': function()
			{
				var pah = {};			// parsed attribute hash
				var attrRules =
				{
					'parse': function(_attr)
					{
						var m = _attr.match(/^\[([\w-_]+)?(\=|\^=|\$=|\*=|\|=|~=|!=)?(.*)\]$/);
						return pah[_attr] = { name: m && m[1], delim: m && m[2], val: m && m[3].replace(/^['"]|["']$/g, '') };						
					},
					
					'=': function(_attr, _val)
					{
						return _attr === _val;
					},

					'^=': function(_attr, _val)
					{
						return _attr.indexOf(_val) === 0;
					},

					'$=': function(_attr, _val)
					{
						var lio = _attr.lastIndexOf(_val);
						return lio !== -1 && lio + _val.length === _attr.length;
					},

					'*=': function(_attr, _val)
					{
						return _attr.indexOf(_val) !== -1;
					},

					'|=': function(_attr, _val)
					{
						return (_attr === _val) || (_attr.indexOf(_val + '-') === 0);
					},

					'~=': function(_attr, _val)
					{
						return (_attr === _val) || contains(_attr.split(' '), _val);
					},

					'!=': function(_attr, _val)
					{
						return _attr !== _val;
					},

					'unknown': function()
					{
						return false;
					}			
				};
			
				return function(elem, attributes)
				{
					var i = attributes.length;
					while (i--)
					{
						var attr = pah[attributes[i]] || attrRules.parse(attributes[i]);
						var actualVal = getAttr(elem, attr.name);
						
						if (!actualVal) return false;
						if (!attr.delim) continue;					
						if (!attrRules[attr.delim || 'unknown'](actualVal, attr.val)) return false;
					}
					return true;
				};
			}(),
			
			'pseudos': function()
			{
				var pph = {};			// parsed pseudo hash
				var pseudoRules = 
				{
					parse: function(_pseudo)
					{
						// [0] = entire string, including parenthetical param (if present)
						// [1] = full pseudo name, not including parenthetical params (even if present)
						// [2] = entire param string (including parens)
						// [3] = entire param string (excluding parens)
						// [4] = an in an + b (if present)
						// [5] = a in an + b (if present)
						// [6] = b in an + b (if present)
						var m = _pseudo.match(/([\w-_]+)\b(\((((-?\d*)n)?([+-]?\d+)?|.*)\))?/);
						var pseudo =
						{
							name: m && m[1],
							param:
							{
								wholeValue: m && m[3],
								a: m && m[5] || 0,
								b: m && m[6] || 0
							}
						}					
						
						if (pseudo.param.wholeValue === 'even') { pseudo.param.a = 2; pseudo.param.b = 0; }
						else if (pseudo.param.wholeValue === 'odd') { pseudo.param.a = 2; pseudo.param.b = 1; }
						
						return pph[_pseudo] = pseudo;
					},
					
					'first-child': child('previous'),
					
					'last-child': child('next'),
					
					'only-child': function(_elem)
					{
						return pseudoRules['first-child'](_elem) && pseudoRules['last-child'](_elem);
					},
					
					'nth-child': function(_elem, _pseudo)
					{
						var cacheConst = 10000;
						var currentTrue = _nthBit.t * cacheConst;
						var bitName = _nthBit.name;
						
						var parent = _elem.parentNode;
						
						var pos = 0;
						if (parent)
						{
							if (parent[bitName + ':parent'] !== _nthBit.t)
							{
								parent[bitName + ':parent'] = _nthBit.t;
								
								var pos = 0;
								var sib, siblings = parent.children || parent.childNodes;
								var i = -1, len = siblings.length;
								while (++i < len)
								{
									if (siblings[i].nodeType === 1)
									{
										pos++;
										siblings[i][bitName] = currentTrue + pos;							
									}
								}
							}
							
							var x = _elem[bitName] - currentTrue - _pseudo.param.b;
							return !_pseudo.param.a && _pseudo.param.b ? x === 0 : (_pseudo.param.a * x >= 0) && (x % (_pseudo.param.a || 1) === 0); 			
						}
						return false;					
					},

					'contains': function(_elem, _pseudo)
					{
						return (_elem.textContent || _elem.innerText || _elem.innerHTML).indexOf(_pseudo.param.wholeValue) !== -1;
					},

					'not': function()
					{
						return false;
					}
				};
				
				function child(direction)
				{
					var sibling = direction + 'Sibling';

					return function(el)
					{
						var sib = el[sibling];
						while (sib && sib.nodeType !== 1)
						{
							sib = sib[sibling];
						}
						return !sib;
					}
				}
					
				return function(elem, pseudos)
				{
					var i = pseudos.length;
					while (i--)
					{
						var pseudo = pph[pseudos[i]] || pseudoRules.parse(pseudos[i]);
						
						if (!pseudoRules[pseudo.name](elem, pseudo))
						{
							return false;
						}
					}			
					return true;
				};
			}(),
		
			' ': function(elems, ss)
			{
				var matched = [];
				var i, len = elems.length;
				for (i = 0; i < len; i++)
				{
					var descendants = simpleFetch(ss, elems[i]);
					matched = matched.concat(descendants);
					if (ss.id && descendants.length === 1) break;
				}

				return unique(matched);
			},
			
			'>': function(elems, ss)
			{
				var matched = [];
				var i, len = elems.length;
				for (i = 0; i < len; i++)
				{
					matched = matched.concat(filter(elems[i].childNodes, ss));
				}
				
				return matched;
			},
			
			'+': function(elems, ss)
			{
				var matched = [];
				var i, len = elems.length;
				for (i = 0; i < len; i++)
				{
					var elem = elems[i];
					var sib = elem.nextSibling;
					while (sib && sib.nodeType !== 1)
					{
						sib = sib.nextSibling;
					}
					if (processSelector(ss, sib))
					{
						matched.push(sib);
					}
				}
				
				return matched;
			},
			
			'~': function(elems, ss)
			{
				_genSibBit.inc();
				var bitName = _genSibBit.name;
				
				var matched = [];
				var i, len = elems.length;
				for (i = 0; i < len; i++)
				{
					var elem = elems[i];
					var sib = elem.nextSibling;
					while (sib && sib[bitName] !== _genSibBit.t)
					{
						if (sib.nodeType === 1)
						{
							sib[bitName] = _genSibBit.t;
							processSelector(ss, sib) && matched.push(sib);						
						}						
						sib = sib.nextSibling;
					}
				}
				
				return matched;
			}
		};

		/*
			The parse rules determine how the CSSParser will actually do its parsing.
			Terminology:
				simpleSelector: Any CSS selector rule that does not involve a combinator, that is: , +, ~, or ' ' (space)
					EXAMPLES:
					div
					div.dog
					div#spot.dog.canine
					img#spot.dog[alt='my dog']
					img.dog:nth-child(2n+1)
					
				complexSelector: Two or more simpleSelectors joined with a combinatorial relationship
					EXAMPLES:
					div+span
					img.dog~p.cat
					#fluffy span + p > em
					
			Notes:
				The parseRules defined below create an array of selector groupings.  Each entry in the selectors array
				represents a single complexSelector, and it most cases, the selectors array will probably contain only
				one entry.
				
				When the input string is a comma separated list of selectors however, then the selectors array will
				contain one entry per complexSelector.
				
					EXAMPLES:
					div, span
					div.dog, span.cat
					div.dog, span.cat, p~p
				
		*/		
		_parseRules = new function()
		{
			var selectors, complexSelector, simpleSelector;
			
			function SimpleSelector()
			{
				// optimization technique:
				// store the property names in a true array, b/c iterating an array is faster than for/in on an object literal
				this.propNames = [];			
			}
			SimpleSelector.prototype.propNames = [];
			SimpleSelector.prototype.storePropertyValue = function(name, val)
			{
				this[name] = val;
				if (!this.propNames[name])
				{
					this.propNames.push(name);
					this.propNames[name] = true;
				}
			};
			SimpleSelector.prototype.storeArrayValue = function(name, val)
			{
				if (!this[name])
				{
					this[name] = [];
				}
				this[name].push(val);
				if (!this.propNames[name])
				{
					this.propNames.push(name);
					this.propNames[name] = true;
				}
			};
			
			var rules =
			{
				// optional rule that the parser will call if it exists
				'preprocessInput': function(input)
				{
					// clean the input by removing extraneous spaces around combinators, start, and end of string
					return input.replace(/\s*([ >+~,])\s*/g, '$1');
				},
				
				// required rule that the parser calls each time .parse is called
				'reset': function()
				{
					// reset the various pieces that make up the parsed object
					selectors = [];
					complexSelector = [];
					simpleSelector = new SimpleSelector();
				},
				
				// requied rule that the parser calls when parsing has completed
				'finish': function()
				{
					// if there is an outstanding simpleSelector with data in it, add it to the current complexSelector
					if (simpleSelector && simpleSelector.propNames.length > 0)
					{
						complexSelector.push(simpleSelector);
					}
					
					// if there an outstanding complexSelector with data in it, add it to the array of selectors
					if (complexSelector.length > 0)
					{
						selectors.push(complexSelector);
					}
					
					// return the array that represents a group of selectors
					return selectors;
				},
				
				// required rule that the parser calls when no other suitable rule was found 
				'default': function(str)
				{
					// in our case, the default rule will be one that matches an Element tag name
					var ruleName = 'tag';
					var m = str.match(/(\w+|\*)/);
					if (m)
					{
						var val = m[0].toUpperCase();
						simpleSelector.storePropertyValue(ruleName, val);
						
						// return the number of characters the parser should advance
						return val.length;
					}
					return null;
				},
				
				// the id rule (matches #someId)
				'#': function(str)
				{	
					var ruleName = 'id';
					var m = str.match(/#([_\-\w]+)/);
					if (m)
					{
						var val = m[1];
						simpleSelector.storePropertyValue(ruleName, val);
						
						// return the number of characters the parser should advance
						// (this would be the id's length including the leading #)
						return m[0].length;
					}
					return null;
				},
				
				// the classes rule (matches .oneClass.twoClass.threeClass.etc)
				'.': function(str)
				{
					var ruleName = 'classes';
					var m = str.match(/\.([_\-\w\d]+)/);
					if (m)
					{
						var val = m[1];
						simpleSelector.storeArrayValue(ruleName, val);
						
						// return the number of characters the parser should advance
						// (this would be the className's length including the leading .)
						return m[0].length;
					}
				},
				
				// the attributes rule (maches [attr=val])
				'[': function(str)
				{
					var ruleName = 'attributes';
					var m = str.match(/(\[.*"\]|.*?\])/);
					if (m)
					{
						var val = m[0];
						simpleSelector.storeArrayValue(ruleName, val);
						
						// return the number of characters the parser should advance
						return val.length;
					}
					return null;			
				},
				
				// the pseudos rule (matches :pseudo)
				':': function(str)
				{
					var ruleName = 'pseudos';
					var m = str.match(/:[\w-_]+\b(\(.*\))?/);
					if (m)
					{
						var val = m[0];
						simpleSelector.storeArrayValue(ruleName, val);
						
						// return the number of characters the parser should advance
						return val.length;
					}
					return null;
				},
				
				// descendant combinator (single space)
				' ': function(str)
				{
					complexSelector.push(simpleSelector, ' ');
					simpleSelector = new SimpleSelector();
					
					// have the parser advance by 1
					return 1;				
				},
				
				// director child combinator			 
				// director child combinator
				'>': function(str)
				{
					if (simpleSelector.propNames.length > 0)
					{
						complexSelector.push(simpleSelector);
					}
					complexSelector.push('>');
					simpleSelector = new SimpleSelector();

					// have the parser advance by 1
					return 1;
				},

				
				// general sibling combinator
				'~': function(str)
				{
					complexSelector.push(simpleSelector, '~');
					simpleSelector = new SimpleSelector();
					
					// have the parser advance by 1
					return 1;
				},
				
				// adjacent sibling combinator
				'+': function(str)
				{
					complexSelector.push(simpleSelector, '+');
					simpleSelector = new SimpleSelector();
					
					// have the parser advance by 1
					return 1;
				},
				
				// selector grouping
				',': function(str)
				{
					complexSelector.push(simpleSelector);
					selectors.push(complexSelector);
					
					complexSelector = [];
					simpleSelector = new SimpleSelector();

					return 1;
				}
			};
			
			return rules;
		};
		
		_parser = new CSSParser(_parseRules);
		////
		
		
		// fetch Utility namespace
		fetch.Internal =
		{
			unique: unique,
			index_of: indexOf,
			contains: contains,
			has_class: _fetchRules.classes,
			get_attr: getAttr
		};
		////
		
		
		return fetch;
	}();
		
